1. Field of the Invention
The present invention relates to cache systems, and, more particularly, to cache replacement monitoring and profiling.
2. Description of the Related Art
Software-controlled prefetching is a technique that may be used to reduce memory latency by attempting to load data into a cache before the data is used for some computation. Most modern architectures provide instructions to explicitly prefetch data. However, the hardware in current implementations of modern architectures provides little feedback to determine the effectiveness of the prefetching. In some cases, unnecessary prefetching may degrade effective memory latency by wasting precious memory bandwidth or by causing unnecessary cache thrashing.
Consider the following sequence of operations (wherein “use” represents either a memory read or a memory write operation, and X, Y and Z are variables with memory addresses corresponding to different cache lines):
(1). use X;
(2). use Y; and
(3). use Z.
Assume that the system uses a 2-way set associative cache with a least recently used (“LRU”) replacement policy and variables X, Y, and Z are all mapped to the same cache line set. If the two cache lines corresponding to X and Y are initially cached in the cache, the use of variable Z would cause a cache miss, indicating that variable Z is a good candidate for prefetching. Consider that “prefetch Z” is inserted before “use Y”:
(1). use X;
(2). prefetch Z;
(3). use Y; and
(4). use Z.
If the cache line corresponding to variable Z arrives before variable Y is used, “prefetch Z” needs to replace variable Y. Consequently, “use Y” will cause a cache miss because variable Y has been replaced by the prefetch. Now consider that “prefetch Z” is inserted just before “use X”:
(1). prefetch Z;
(2). use X;
(3). use Y; and
(4). use Z.
In the worst case, “prefetch Z” will replace variable X causing “use X” to generate a cache miss. When variable X is brought into the cache, variable X will replace variable Y, causing “use Y” to generate a cache miss that will replace variable Z before variable Z is used. In a better but still bad case, “prefetch Z” will replace variable Y causing a cache miss on “use Y” and subsequently replace variable Z, which will cause a cache miss on “use Z”. The performance problems associated with prefetching and cache conflicts can be difficult to understand and track.